//******************************************
// Program: Project 1
// Name: Douglas Kirby
// CS 317
// Project due date: 10/5/10
// Use QuickSort to sort a 30 member and
// a 100 member array
//******************************************

// includes
#include <fstream>
#include "time.h"
#include <cstdlib>

using namespace std;

// function declaration for opening output file
void OpenOutfile(ofstream&);
// function declaration for closing output file
void CloseOutfile(ofstream&);
// function declaration for array output
void OutputArray(int OutArray[], int, ofstream&);
// function declaration for QuickStart
void QuickStart(int OutArray[], int, int&);
// function declaration for QuickSort
int QuickSort(int OutArray[], int, int, int&);
// function declaration for partition
int Partition(int[], int , int, int&);
// function declaration for swap
void Swap(int A[], int, int);

int main()
{
 // variable declaration for output filestream
 ofstream Outfile;
 // variable declaration for comparisons
 int Comparisons = 0;
 // variable declaration for count
 int count = 0;
 // variable declaration for small array
 int SmallArray[30] = {16494, 17213, 31449, 28321, 30978, 10691, 6249, 1462, 32631, 6249, 28234, 24225, 30354, 23854, 30898, 4753, 28231, 27667, 25483, 4554, 6249, 15848, 32262, 8477, 30898, 10935, 23736, 20663, 6249, 20514};
 // seeds the random number generator with the system clock
 srand (time(NULL));
 // variable declaration for large array
 int LargeArray[100];
 //randomly generate large array
 while(count < 100)
 {
  // randomly generates the large array
  LargeArray[count] = rand();
  // adds 1 to count
  count ++;
 }
 // function call for output openOutfile function
 OpenOutfile(Outfile);
 // file output
 Outfile << "First Data Set:\n\n";
 Outfile << "Original Unsorted Array:\n\n";
 //function call for array output
 OutputArray(SmallArray, 30, Outfile);
 // file output
 Outfile << "\nSorted array by Quick Sort:\n\n";
 // function call to start the sorting
 QuickStart(SmallArray, 30, Comparisons);
 // function call for array ouput
 OutputArray(SmallArray, 30, Outfile);
 // comparison output
 Outfile << "\nTotal Comparisons Taken: " << Comparisons << "\n\n";
 // file output
 Outfile << "Second Data Set:\n\n";
 Outfile << "Original Unsorted Array:\n\n";
 // function call for array ouput
 OutputArray(LargeArray, 100, Outfile);
 // file output
 Outfile << "\nSorted array by Quick Sort:\n\n";
 // function call to start the sorting
 QuickStart(LargeArray, 100, Comparisons);
 // function call for array ouput
 OutputArray(LargeArray, 100, Outfile);
 // comparison output
 Outfile << "\nTotal Comparisons Taken: " << Comparisons;
 // function call for output closefile function
 CloseOutfile(Outfile);
 // end of program
 return 0;
}

// openfile (output) function
void OpenOutfile(ofstream& Outfile)
{
 // variable declarations
 string OutputFile = "drk0002.txt"; // output file
 // opens input filestream
 Outfile.open(OutputFile.c_str());
}

// closefile (output) function
void CloseOutfile(ofstream& Outfile)
{
 // closes file and resets input stream
 Outfile.close();
 // clears the input file stream
 Outfile.clear();
}

// array output function
void OutputArray(int OutArray[], int Elements, ofstream& Outfile)
{
 // function declaration for count
 int count = 0;
 // checks if count is less than Elements
 while(count < Elements)
 {
  // outputs the array to the file
  Outfile << OutArray[count];
  // skips a line
  Outfile <<"\n";
  // adds 1 to count
  count++;
 }
}

// sorting function start
void QuickStart(int OutArray[], int size, int& Comparisons)
{
 // variable declarations
 int l = 0, r = size-1;
 // initialize comparison
 Comparisons = 0;
 // get the value for comparisons from quicksort
 Comparisons = QuickSort(OutArray, l, r, Comparisons);
}

// Quicksort function
int QuickSort(int OutArray[], int l, int r, int& Comparisons)
{
 // checks if l is less than r
 if(l<r)
 {
  // get s from partition
  int s = Partition(OutArray, l, r, Comparisons);
  // run quicksort for the left side
  QuickSort(OutArray, l, s-1, Comparisons);
  // run quicksort for the right side
  QuickSort(OutArray, s+1, r, Comparisons);
 }
return Comparisons;
}

// Partition function
int Partition(int A[], int l, int r, int& Comparisons)
{
 {
  // variable declarion
  int  p = l;
  // set the pivot
  int pivot = A[l];
  // check if i is les than or equal to r
  for(int i = l+1; i <= r; i++)
  {
   // adds 1 to comparisons
   Comparisons++;
   // checks if A[i] less than or equal to pivot
   if( A[i] <= pivot )
   {
    // adds 1 to p
    p++;
    // runs swap
    Swap(A, i, p);
   }
  }
  // runs swap
  Swap(A, p, l);
  // returns p
  return p;
 }
}

// swap function
void Swap(int A[], int i, int j)
{
 // makes a temp int of A[j]
 int temp = A[j];
 // sets A[j] = A[i]
 A[j] = A[i];
 // sets A[i] = temp
 A[i] = temp;
}
